1. Field of the Invention
This invention relates to a range-image processing apparatus for forming polygon data which approximately describe the surface shape of an object represented by a range image from the input range image.
2. Description of the Related Art
Before describing a conventional technique, a brief explanation of technical terms relating to the present invention will be provided.
First, a "range image" indicates an image in which the vertical distance between each point on the surface of an object measured by a distance-measuring sensor and a reference plane is provided as a pixel (picture element) value. As a data format, distance value Z is stored for each point (X, Y) on a square two-dimensional lattice. Such data have recently been utilized in the field of computer vision and computer graphics.
Next, "polygon data" indicate data for approximately representing the surface shape of an object by combining polygons, each of which is present on the same plane. FIG. 7 illustrates a polygon-data structure which uses triangles as polygons. This data structure is composed of two portions. In the first portion, information relating to vertices constituting each polygon is assigned. In this example, for each vertex, in addition to (x,y,z) value of vertex information, which is indispensable data, normal-vector value (Nx,Ny,Nz) at the vertex is also provided as optional data. In the second portion, connection information of edge lines constituting each polygon is indicated for the assigned vertex information. The number n (3 in this example) of vertices constituting each polygon is first provided followed by n vertex numbers representing respective vertices constituting the polygon.
A range-image processing apparatus has, for example, been devised, in which three-dimensional position coordinate data of the surface of an object are input from a three-dimensional-coordinate measuring device, such as a laser range finder or the like, the obtained range image is uniformly divided with a fixed equidistant square lattice, and polygon data for approximating the surface of the object in units of a square obtained by connecting the vertices of adjacent lattice points are found.
In the above-described conventional apparatus, however, since polygons of the same kind are utilized for the entire range image, the number of polygons and the amount of data increase if it is intended to improve approximation accuracy for an object having a complicated shape.
On the other hand, if it is intended to suppress the amount of data to a certain degree, the size of each polygon must be increased while reducing the number of polygons. Hence, accuracy in approximation deteriorates, and details in the shape of the object cannot be reproduced.
In addition, if only one non-closed edge is present in an edge map formed from the range image, polygon data cannot be formed.
Furthermore, in the above-described conventional approach, adjacent pixels must always be subjected to edge detection processing so that even for an object having a very simple shape, a large amount of useless calculation must, in some cases, be performed. In addition, since a curved surface is recognized as one region, the recognition result cannot be directly used for forming polygon data when it is intended to approximate the shape of an object by planes. Moreover, since each edge which must be represented as a line segment is represented by connection of points on the image, a large amount of storage region is required, and it is difficult to process the edge as a line segment.